/*
题目：两点之间的磁力
两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力。
Rick 有 n 个空的篮子，第 i 个篮子的位置在 position[i] ，Morty 想把 m 个球放到这些篮子里，使得任意两球间 最小磁力 最大。

已知两个球如果分别位于 x 和 y ，那么它们之间的磁力为 |x - y| 。

给你一个整数数组 position 和一个整数 m ，请你返回最大化的最小磁力。
https://leetcode.cn/problems/magnetic-force-between-two-balls/description/
 */
public class MaxDistance {
    int n ;
    public int maxDistance(int[] position, int m) {
        this.n = position.length;
        // 二分答案
        // 尽量让这些球分布的越远越好
        Arrays.sort(position);
        int left = 1, right = position[position.length - 1];
        while (left <= right) {
            int gus = left + ((right - left) >> 1); // 猜测的最小磁力
            if (check(position, m, gus) == 1) { // 如果大了
                right = gus - 1;
            } else { // 如果小了
                left = gus + 1;
            }
        }
        return left - 1;
    }

    // 检验猜测 最小磁力 的大概值
    private int check(int[] position, int m, int gus) {
        int cur = position[0]; // 上一个球的位置
        int i = 1;   // position 数组的下标位置
        while (m > 1 && i < n) { // 默认第一个就带有球
            while (i < n && position[i] - cur < gus) {
                i ++;
            }
            // 如果满足上述循环了
            if (i < n) {
                cur = position[i ++]; // 更新 cur 值
                m --;
            }
        }
        // 如果 m 能够到达 1，说明能恰好满足，或者太小；否则说明猜的太大
        return m == 1 ? -1 : 1;
    }
}
